import java.util.Arrays;
import java.util.Random;

public class Sort {
    static class Node {
        int comCount = 0;//记录比较次数
        int moveCount = 0;//记录移动次数
    }

    /**
     * 直接插入排序
     *
     * @param
     */
    public static void insertSort(int[] array) {
        Node node = new Node();
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                node.comCount++;
                if (array[j] > tmp) {
                    node.moveCount++;
                    array[j + 1] = array[j];
                } else {
//                    array[j+1] = tmp;
                    break;
                }

            }
            node.moveCount++;
            array[j + 1] = tmp;


        }
        System.out.println("直接插入排序 比较次数 : " + node.comCount);
        System.out.println("直接插入排序 移动次数 : " + node.moveCount++);

    }

    /**
     * 希尔排序
     *
     * @param array
     */
    public static void shellSort(int[] array) {
        Node node = new Node();
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 2;
            shell(array, gap, node);
        }
        System.out.println("希尔排序 比较次数 : " + node.comCount);
        System.out.println("希尔排序 移动次数 : " + node.moveCount);
    }

    public static void shell(int[] array, int gap, Node node) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                node.comCount++;
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                    node.moveCount++;
                } else {
                    break;
                }
            }
            node.moveCount++;
            array[j + gap] = tmp;
        }


    }


    /**
     * 快速排序
     *
     * @param array
     */
    public static void quickSort(int[] array) {
        Node node = new Node();
        quickSort2(array, 0, array.length - 1, node);
        System.out.println("快速排序 比较次数 : " + node.comCount);
        System.out.println("快速排序 移动次数 : " + node.moveCount++);
    }

    public static void quickSort2(int[] array, int l, int r, Node node) {
        if (l >= r) {
            return;
        }
        //选择基准元素
        int key = array[new Random().nextInt(r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (array[i] < key) {
                swap(array, left + 1, i, node);
                left++;
                i++;
            } else if (array[i] == key) {
                i++;
            } else {
                swap(array, right - 1, i, node);
                right--;
            }
            node.comCount++;
        }
        quickSort2(array, l, left, node);
        quickSort2(array, right, r, node);
    }

    private static void swap(int[] array, int i, int j, Node node) {
        node.moveCount += 3;
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    /**
     * 堆排
     *
     * @param array
     */
    public static void heapSort(int[] array) {
        Node node = new Node();
        //创建大根堆
        createBigHeap(array, node);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end, node);
            shiftDown(array, 0, end, node);
            end--;
        }
        System.out.println("堆排序 比较次数 : " + node.comCount);
        System.out.println("堆排序 移动次数 : " + node.moveCount);


    }

    public static void createBigHeap(int[] array, Node node) {

        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length, node);

        }
    }

    public static void shiftDown(int[] array, int parent, int len, Node node) {
        int child = parent * 2 + 1;
        while (child < len) {
            node.comCount++;
            if (child + 1 < len && array[child] < array[child + 1]) {

                child++;
            }
            node.comCount++;
            if (array[child] > array[parent]) {
                swap(array, child, parent, node);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }

    }


    /**
     * 归二路排序
     *
     * @param array
     */
    public static void mergeSort(int[] array) {
        Node node = new Node();
        mergeSort2(array, 0, array.length - 1, node);
        System.out.println("归并 比较次数 : " + node.comCount);
        System.out.println("归并 移动次数 : " + node.moveCount);
    }

    private static void mergeSort2(int[] array, int left, int right, Node node) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort2(array, left, mid, node);
        mergeSort2(array, mid + 1, right, node);
        int[] tmp = new int[right - left + 1];
        int l = left, r = mid + 1, i = 0;
        while (l <= mid && r <= right) {
            node.comCount++;
            if (array[l] < array[r]) {
                tmp[i] = array[l];
                node.moveCount++;
                l++;
                i++;
            } else {
                tmp[i] = array[r];
                node.moveCount++;
                r++;
                i++;
            }
        }
        while (l <= mid) {
            tmp[i++] = array[l++];
            node.moveCount++;
        }
        ;
        while (r <= right) {
            tmp[i++] = array[r++];
            node.moveCount++;
        }
        //还原
        for (int j = left; j <= right; j++) {
            array[j] = tmp[j - left];
            node.moveCount++;
        }
    }



    public static void main(String[] args) {
        int[] array = {5,1,1,0,0};
//        int[] array = {5,2,3,1};
//        int[] array = {5,4,3,2,1};
//        int[] array = {1,2,3,4,5};
//        insertSort(array);
//        System.out.println(Arrays.toString(array));
//        quickSort(array);
//        System.out.println(Arrays.toString(array));
//        mergeSort(array);
//        System.out.println(Arrays.toString(array));
//        shellSort(array);
//        System.out.println(Arrays.toString(array));
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }
}
